package Solutions

import "strings"

type dTreeNode struct {
	v     byte
	Child map[byte]*dTreeNode
}

func NewDTreeNode(v byte) *dTreeNode {
	return &dTreeNode{
		v,
		map[byte]*dTreeNode{},
	}
}
func createDTree(strs map[string]byte) *dTreeNode {
	root := &dTreeNode{
		0,
		map[byte]*dTreeNode{},
	}
	for str, b := range strs {
		now := root
		for j := 0; j < len(str); j++ {
			if v, ok := now.Child[str[j]]; ok {
				now = v
			} else {
				var nd *dTreeNode
				if j == len(str)-1 {
					nd = NewDTreeNode(b)
				} else {
					nd = NewDTreeNode(0)
				}

				now.Child[str[j]] = nd
				now = nd
			}
		}
	}
	return root

}

func entityParser(text string) string {
	sb := strings.Builder{}
	stack := make([]byte, 8)
	st := -1
	var mp = map[string]byte{
		"&quot;":  '"',
		"&apos;":  '\'',
		"&amp;":   '&',
		"&gt;":    '>',
		"&lt;":    '<',
		"&frasl;": '/',
	}
	dTree := createDTree(mp)
	for i := 0; i < len(text); {
		if text[i] != '&' {
			sb.WriteByte(text[i])
			i++
		} else {
			now := dTree.Child['&']
			i++
			st++
			stack[st] = '&'
			for i < len(text) {
				if v, ok := now.Child[text[i]]; ok {
					now = v
					if now.v != 0 {
						st = -1
						sb.WriteByte(now.v)
					} else {
						st++
						stack[st] = text[i]
					}
				} else {
					for j := 0; j <= st; j++ {
						sb.WriteByte(stack[j])
					}
					st = -1
					break
				}
				i++
			}
		}
	}
	for j := 0; j <= st; j++ {
		sb.WriteByte(stack[j])
	}
	return sb.String()
}
